Minimal Polynomial

Jordan Chains

Let A be an nxn matrix and Ā be its Jordan canonical form.

ACn×nAˉ=J=B1ABCn=N(Aλ1I)m1N(AλkI)mk      We look for basis vectors for N((AλiI)mi)B=[B1B2Bn]Bi=[bi2bi3biri] where bi,,biri have to be basis vectors for N((AλiI)mi) A \in \mathbb{C}^{n \times n} \\ \bar A = J = B^{-1}AB \\ \mathbb{C}^n = N(A-\lambda_1I)^{m_1} \oplus \cdots \oplus N(A-\lambda_kI)^{m_k} \\ \ \ \ \ \ \ \text{We look for basis vectors for } N((A - \lambda_iI)^{m_i}) \\ B = \begin{bmatrix} B_1 & B_2 & \cdots & B_n \end{bmatrix} \\ B_i = \begin{bmatrix} b_i^2 & b_i^3 & \cdots & b_i^{r_i} \end{bmatrix} \text{ where } b_i, \cdots, b_i^{r_i} \text{ have to be basis vectors for } N((A-\lambda_iI)^{m_i})

Let Mi:=AλiIM_i := A - \lambda_iI , and let's choose a vector x such that xN(Mij)x \in N(M_i^j) or Mijx=0M_i^jx = 0 , but xN(Mij1)x \notin N(M_i^{j-1})

Now consider the chain of vectors x,Mix,Mi2x,,Mij1xx, M_ix, M_i^2x, \cdots, M_i^{j-1}x , which is linearly independent. We can see this by contradiction. Suppose that the chain is linearly dependent. Then there exists a vector MikxM_i^kx such that Mikx=l=0k1clMilxM_i^kx = \sum_{l=0}^{k-1} c_lM_i^lx , where clCc_l \in \mathbb{C} . But then Mikx=0M_i^kx = 0 , which is a contradiction. Thus, the chain is linearly independent.

{Mimi1x,Mimi2x,,Mix,x} is linearly independent \{ M_i^{m_i-1}x, M_i^{m_i-2}x, \cdots, M_ix, x \} \text{ is linearly independent}
┌──────────────────────────────────┬──────────┐
│                                  │  N(Σᵢᵐ)  │
│                       - x        └──────────┤
│      ┌───────────────────────────┬──────────┤
│      │                           │ N(Σᵢᵐ⁻¹) │
│      │               - Σᵢx       └──────────┤
│      │      ┌────────────────────┬──────────┤
│      │      │                    │ N(Σᵢ²)   │
│      │      │       - Σᵢᴹᶦ⁻²     └──────────┤
│      │      │    ┌───────────────┬──────────┤
│      │      │    │               │ N(Σᵢ)    │
│      │      │    │               └──────────┤
│      │      │    │ - Σᵢᴹᶦ⁻¹                 │
└──────┴──────┴────┴──────────────────────────┘

Example: Find the Jordan canonical form of A=[111132001]A = \begin{bmatrix} 1 & 1 & -1 \\ -1 & 3 & 2 \\ 0 & 0 & 1 \end{bmatrix}

Solution:

d(s)=det(sIA)=(s1)[(s3)(s1)+1]=(s2)2(s1) d(s) = \text{det}(sI - A) = (s-1)[(s-3)(s-1)+1] = (s-2)^2(s-1)

λ1=2λ2=1 \lambda_1 = 2 \text{, } \lambda_2 = 1

Σ1 =  A2I  =[111112001]\Sigma_1 \ = \ \ A-2I \ \ = \begin{bmatrix} -1 & 1 & -1 \\ -1 & 1 & 2 \\ 0 & 0 & -1 \end{bmatrix}  dim N(Σ1)=32=1r1=2 \text{ dim }N ( \Sigma_1) = 3-2 = 1 \neq r_1 = 2

Σ12=(A2I)2=[111112001][111112001]=[004001001] dim N(Σ12)=31=2=r1 \Sigma_1^2 = (A-2I)^2 = \begin{bmatrix} -1 & 1 & -1 \\ -1 & 1 & 2 \\ 0 & 0 & -1 \end{bmatrix} \begin{bmatrix} -1 & 1 & -1 \\ -1 & 1 & 2 \\ 0 & 0 & -1 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 4 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix} \text{ dim }N(\Sigma_1^2) = 3-1 = 2 = r_1

No need to check Σ2\Sigma_2 because r2=1r_2 = 1

m(s)=(s2)2(s1)=d(s) m(s) = (s-2)^2(s-1) = d(s)

From the minimal polynomial, we can see that the Jordan canonical form will have a 2x2 block for λ1=2\lambda_1 = 2 and a 1x1 block for λ2=1\lambda_2 = 1

Aˉ=J=[210020001] PJ=AP \bar A = J = \begin{bmatrix} 2 & 1 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix} \rightarrow \ P J = A P

Now we will construct the chain of vectors, which will be used to construct the basis vectors.

xN(Σ12) but xN(Σ1) x \in N(\Sigma_1^2) \text{ but } x \notin N(\Sigma_1)

Σ12x=0[004001001][x1x2x3]=[000]x3=0 \Sigma_1^2x = 0 \rightarrow \begin{bmatrix} 0 & 0 & 4 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \rightarrow x_3 = 0

Σ1x0[111112001][x1x20][000]x1x2 \Sigma_1x \neq 0 \rightarrow \begin{bmatrix} -1 & 1 & -1 \\ -1 & 1 & 2 \\ 0 & 0 & -1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ 0 \end{bmatrix} \neq \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \rightarrow x_1 \neq x_2

Select x=[100]x = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} such that xN(Σ12) but xN(Σ1)x \in N(\Sigma_1^2) \text{ but } x \notin N(\Sigma_1)

The chain of vectors for λ1=2\lambda_1 = 2 is

{ Σ1x , x }={[110],[100]} \Big \{ \ \Sigma_1x \ , \ x \ \Big \} = \Bigg \{ \begin{bmatrix} -1 \\ -1 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} \Bigg \}

┌──────────────────────────────────┬──────────┐
│                                  │ N(Σ₁²)   │
│                     - x          └──────────┤
│                  ┌───────────────┬──────────┤
│                  │               │ N(Σ₁)    │
│                  │               └──────────┤
│                  │ - Σ₁x                    │
└──────────────────┴──────────────────────────┘

Now we will construct the chain of vectors for λ2=1\lambda_2 = 1

Σ2=AI=[011122000] \Sigma_2 = A - I = \begin{bmatrix} 0 & 1 & -1 \\ -1 & 2 & 2 \\ 0 & 0 & 0 \end{bmatrix}  dim N(Σ2)=32=1=r2 \text{ dim }N(\Sigma_2) = 3-2 = 1 = r_2

yN(Σ2) y \in N(\Sigma_2)

Σ2y=0[011122000][y1y2y3]=[000]y=[411] \Sigma_2y = 0 \rightarrow \begin{bmatrix} 0 & 1 & -1 \\ -1 & 2 & 2 \\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \rightarrow y = \begin{bmatrix} 4 \\ 1 \\ 1 \end{bmatrix}

The chain of vectors for λ2=1\lambda_2 = 1 is

{y}={[411]} \Big \{y \Big \} = \Bigg \{\begin{bmatrix} 4 \\ 1 \\ 1 \end{bmatrix} \Bigg \}

┌──────────────────────────────────┬──────────┐
│                                  │ N(Σ₂)    │
│                                  └──────────┤
│                                  - y        │
└─────────────────────────────────────────────┘

Now we will construct the change of basis matrix PP, or BB in the general case.

P=[  Σ1x     x     y  ]=[114101001] P = \begin{bmatrix} \ \ \Sigma_1x \ \ \ \ \vert & \ x & \vert \ \ \ \ \ y \ \ \end{bmatrix} = \begin{bmatrix} -1 & 1 & 4 \\ -1 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix}

J=P1AP = [114101001]1[111132001][114101001]=[210020001] J = P^{-1}AP \ = \ \begin{bmatrix} -1 & 1 & 4 \\ -1 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & -1 \\ -1 & 3 & 2 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} -1 & 1 & 4 \\ -1 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 1 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix}

AP=PAˉ    [111132001][114111001]=[114111001][210020001] A P = P \bar A \implies \begin{bmatrix} 1 & 1 & -1 \\ -1 & 3 & 2 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} -1 & 1 & 4 \\ -1 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} -1 & 1 & 4 \\ -1 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix}


Special Case I

AA has a single eigenvalue λi\lambda_i and mi=ri m_i = r_i

 ┌─────────────────────────┬──────┬───────┬──────┐
 │ N(Σᵢ)        - Σᵢᵐ⁻¹x   │      │ ..... │      │
 ├─────────────────────────┘      │       │      │
 │ N(Σᵢ²)          - Σᵢᵐ⁻²x       │       │      │
 ├────────────────────────────────┘..     │      │
 │ .                                  ..  │      │
 ├────────────────────────────────────────┘      │
 │ N(Σᵢᵐᶦ)                   - x                 │
 └───────────────────────────────────────────────┘

For this case, we can see that m(s)=d(s)m(s) = d(s) , which means that the Jordan canonical form will have a single block for λ\lambda , and the size of the block will be mi=rim_i = r_i . This is because the minimal polynomial is the product of the linear factors of the characteristic polynomial, and the characteristic polynomial is the product of the eigenvalues. Since there is only one eigenvalue, the minimal polynomial will be the same as the characteristic polynomial.

Aˉ=J=[λ1000λ10000λ] \bar A = J = \begin{bmatrix} \lambda & 1 & 0 & \cdots & 0 \\ 0 & \lambda & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \lambda \end{bmatrix}

consider the case: {Σimi1x,Σimi2x,,Σix,x}\Big \{ \Sigma_i^{m_i-1}x, \Sigma_i^{m_i-2}x, \cdots, \Sigma_ix, x \Big \} where it is sufficient to span N(Σimi)N(\Sigma_i^{m_i}) , which is the same as N(Σimi1)N(\Sigma_i^{m_i-1}) , which is the same as N(Σimi2)N(\Sigma_i^{m_i-2}) , and so on. There are rir_i vectors in this chain, which is the same as the dimension of N(Σimi)N(\Sigma_i^{m_i}) .


Special Case II

AA has a single eigenvalue λi\lambda_i and mi=1 m_i = 1

 ┌───────────────────────────────────────────────┐
 │ N(Σᵢ)           - x₃                          │
 │                      - x₂                     │
 │                           - x₁                │
 └───────────────────────────────────────────────┘

For this case, we can see that m(s)=(sλi)m(s) = (s-\lambda_i) , which means that the Jordan canonical form will have a single block for λ\lambda , and the size of the block will be mi=1m_i = 1 . This is because the minimal polynomial is the product of the linear factors of the characteristic polynomial, and the characteristic polynomial is the product of the eigenvalues. Since there is only one eigenvalue, the minimal polynomial will be the same as the characteristic polynomial. The number of chains will be equal to the dimension of N(Σi)N(\Sigma_i), which is rir_i.

dim N(Σi)=ri \text{dim }N(\Sigma_i) = r_i

chain 1={x1}chain 2={x2}           chain ri={xri} \text{chain }1 = \Big \{ x_1 \Big \} \\ \text{chain }2 = \Big \{ x_2 \Big \} \\ \ \ \ \ \ \ \ \ \ \ \ \vdots \\ \text{chain }r_i = \Big \{ x_{r_i} \Big \}

J=[λ0000λ00000λ] J = \begin{bmatrix} \lambda & 0 & 0 & \cdots & 0 \\ 0 & \lambda & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \lambda \end{bmatrix}


Example: Given mi=6m_i = 6 and ri=8r_i = 8 , Find the largest K value such that yN(ΣiK)y \in N(\Sigma_i^K) but yN(ΣiK1)y \notin N(\Sigma_i^{K-1})

 ┌─────────────────────────┬──────┬───────┬──────┬──────┬───────┐
 │ N(Σᵢ)    -Σᵢy   - Σᵢ⁵   │      │       │      │      │       │
 ├─────────────────────────┘      │       │      │      │       │
 │ N(Σᵢ²)      -y         - Σᵢ⁴x  │       │      │      │       │
 ├────────────────────────────────┘       │      │      │       │
 │ N(Σᵢ³)                         - Σᵢ³x  │      │      │       │
 ├────────────────────────────────────────┘      │      │       │
 │ N(Σᵢ⁴)                              - Σᵢ²x    │      │       │
 ├───────────────────────────────────────────────┘      │       │
 │ N(Σᵢ⁵)                                     - Σᵢx     │       │
 ├──────────────────────────────────────────────────────┘       │
 │ N(Σᵢ⁶)                                           - x         │
 └──────────────────────────────────────────────────────────────┘

First chain {Σi5x,Σi4x,Σi3x,Σi2x,Σix,x} \Big \{ \Sigma_i^5x, \Sigma_i^4x, \Sigma_i^3x, \Sigma_i^2x, \Sigma_ix, x \Big \} has rir_i vectors, which is the same as the dimension of N(Σi6)N(\Sigma_i^6)

Second chain {Σiy,y} \Big \{ \Sigma_i y, y \Big \} has 2 vectors, which is the same as the dimension of N(Σi1)N(\Sigma_i^1)

B=[Σi5xΣi4xΣi3xΣi2xΣixxΣiyy] B = \begin{bmatrix} \Sigma_i^5x & \Sigma_i^4x & \Sigma_i^3x & \Sigma_i^2x & \Sigma_ix & x & \Sigma_iy & y \end{bmatrix}

J=[λ10000000λ10000000λ10000000λ10000000λ10000000λ00000000λ10000000λ] J = \begin{bmatrix} \lambda & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & \lambda & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & \lambda & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \lambda & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \lambda & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \lambda & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & \lambda & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \lambda \end{bmatrix}


Example: Let AC6×6A \in \mathbb{C}^{6\times 6} with a single eigenvalue. m(s)=(sλi)3m(s)=(s-\lambda_i)^3 , dim N(Σi)=2\text{dim }N(\Sigma_i) = 2 , Find the Jordan canonical form of AA and construct the change of basis matrix BB.

Solution:

d(s)=(sλi)6dim (v)=6 single eigenvalue λi d(s) = (s - \lambda_i )^6 \rightarrow \text{dim }(v) = 6 \text{ single eigenvalue } \lambda_i

dim N(Σi)=2     There are 2 Jordan blocks or chains  \text{dim }N(\Sigma_i) = 2 \implies \text{ There are 2 Jordan blocks or chains }

m(s)=(sλi)3     The size of largest Jordan block is 3×3 m(s) = (s-\lambda_i)^3 \implies \text{ The size of largest Jordan block is } 3 \times 3

Then we would have 2 Jordan blocks of size 3x3. The change of basis matrix BB would be composed of the basis vectors.

Aˉ=J=[λ100000λ100000λ000000λ100000λ100000λ] \bar A = J = \begin{bmatrix} \lambda & 1 & 0 & 0 & 0 & 0 \\ 0 & \lambda & 1 & 0 & 0 & 0 \\ 0 & 0 & \lambda & 0 & 0 & 0 \\ 0 & 0 & 0 & \lambda & 1 & 0 \\ 0 & 0 & 0 & 0 & \lambda & 1 \\ 0 & 0 & 0 & 0 & 0 & \lambda \end{bmatrix}

Jordan chains for λi\lambda_i are {Σi2x,Σix,x} \Big \{ \Sigma_i^2x, \Sigma_ix, x \Big \} and {Σi2y,Σiy,y} \Big \{ \Sigma_i^2y, \Sigma_iy, y \Big \}

B=[Σi2xΣixxΣi2yΣiyy] B = \begin{bmatrix} \Sigma_i^2x & \Sigma_ix & x & \Sigma_i^2y & \Sigma_iy & y \end{bmatrix}

Try to find xx and yy such that xN(Σi2)x \in N(\Sigma_i^2) but xN(Σi)x \notin N(\Sigma_i) and yN(Σi)y \in N(\Sigma_i)

ASK FOR HELP FOR NEXT


Example: Let A=[1100010000101102]A = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ -1 & 1 & 0 & 2 \end{bmatrix} Find the characteristic polynomial, minimal polynomial, Jordan canonical form and the basis for AA.

Solution:

d(s)=det(sIA)=(s1)3(s2) d(s) = \text{det}(sI - A) = (s-1)^3(s-2)

For the minimal polynomial, we need to check the null space of AλiIA - \lambda_iI for each eigenvalue.

Σ1=  AI  =[0100000000001101]dim N(Σ1)=42=2r1 \Sigma_1 = \ \ A - I \ \ = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ -1 & 1 & 0 & 1 \end{bmatrix} \text{dim }N(\Sigma_1) = 4-2 = 2 \neq r_1

Σ12=(AI)2=[0000000000001001]dim N(Σ12)=41=3=r1 \Sigma_1^2 = (A - I)^2 = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 \end{bmatrix} \text{dim }N(\Sigma_1^2) = 4-1 = 3 = r_1

Σ2=  A2I =[1100010000101100]dim N(Σ2)=41=3=r2 \Sigma_2 = \ \ A - 2I \ = \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ -1 & 1 & 0 & 0 \end{bmatrix} \text{dim }N(\Sigma_2) = 4-1 = 3 = r_2

m(s)=(s1)2(s2) m(s) = (s-1)^2(s-2) Largest Jordan block is 2x2

Aˉ=J=[1100010000100002] \bar A = J = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 2 \end{bmatrix}

Jordan chains for λ1=1\lambda_1 = 1 are {Σ1x,x} \Big \{ \Sigma_1x, x \Big \}

choose x=[1101]x = \begin{bmatrix} 1 \\ 1 \\ 0 \\ 1 \end{bmatrix} Then {Σ1x,x}={[1001],[1101]} \Big \{ \Sigma_1x, x \Big \} = \Big \{ \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 0 \\ 1 \end{bmatrix} \Big \}

choose y=[0010]y = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} Then {y}={[0010]} \Big \{y \Big \} = \Big \{ \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} \Big \}

choose z=[0001]z = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} Then {z}={[0001]} \Big \{z \Big \} = \Big \{ \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} \Big \}

B=[Σ1xxyz]=[1100010000101101] B = \begin{bmatrix} \Sigma_1x & x & y & z \end{bmatrix} = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{bmatrix}


#EE501 - Linear Systems Theory at METU